

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author Embrace
 * @version 1.0.0
 * @ClassName TestUtil.java
 * @git https://gitee.com/EmbraceQAQ
 * @createTime 2020年12月22日 08:38:00
 */
public class TestUtil {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }

    public static void main(String[] args) {
        TreeNode root =new TreeNode(1);
        root.setLeft(new TreeNode(2));
        root.setRight(new TreeNode(3));
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            System.out.println("empty");
        }
        //栈1来存储右节点到左节点的顺序
        Stack<TreeNode> stack1 = new Stack<>();
        //栈2来存储左节点到右节点的顺序
        Stack<TreeNode> stack2 = new Stack<>();

        //根节点入栈
        stack1.push(root);

        //每次循环中，都是一个栈为空，一个栈不为空，结束的条件两个都为空
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            // 存储这一个层的数据
            List<Integer> subList = new ArrayList<>();
            TreeNode cur = null;
            //栈1不为空，则栈2此时为空，需要用栈2来存储从下一层从左到右的顺序
            if (!stack1.isEmpty()) {
                //遍历栈1中所有元素，即当前层的所有元素
                while (!stack1.isEmpty()) {
                    cur = stack1.pop();
                    //存储当前层所有元素
                    subList.add(cur.val);

                    if (cur.left != null) {
                        //左节点不为空加入下一层
                        stack2.push(cur.left);
                    }
                    if (cur.right != null) {
                        //右节点不为空加入下一层
                        stack2.push(cur.right);
                    }
                }
                list.add(subList);
                //栈2不为空，则栈1此时为空，需要用栈1来存储从下一层从右到左的顺序
            }else {
                while (!stack2.isEmpty()) {
                    cur = stack2.pop();
                    subList.add(cur.val);
                    //右节点不为空加入下一层
                    if (cur.right != null) {
                        stack1.push(cur.right);
                    }
                    //左节点不为空加入下一层
                    if (cur.left != null) {
                        stack1.push(cur.left);
                    }
                }
                list.add(subList);
            }
        }
        list.forEach(System.out::println);
    }
}
